﻿#define  _CRT_SECURE_NO_WARNINGS
//对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
//
//例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。
//给你一个整数 num ，输出它的补数。
//
//
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/number-complement
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//普通法
int findComplement(int num) {
    int sum = 0;
    int n = 0;
    while (num) {
        int c = num % 2;
        num /= 2;
        n++;
        if (c == 1) {
            sum += 0;
        }
        else if (c == 0) {
            sum += pow(2, n - 1);
        }

    }
    return sum;
}
//模拟法：
int findComplement(int num) {
    int i = 0;
    int pos = 0;
    for (i = 30;i >= 0;i--) {
        if (1 & (num >> i)) {
            pos = i;
            break;
        }
    }
    for (i = pos;i >= 0;i--) {
        num = num ^ (1 << i);
    }
    return num;
}
//移位法：

int findComplement(int num) {
    long t = 1;
    while (t <= num) {
        t <<= 1;
    }
    return (num ^ (t - 1));
}
//每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。
//
//二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。
//
//给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/complement-of-base-10-integer
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int findComplement(int num) {
    long t = 1;
    while (t <= num) {
        t <<= 1;
    }
    return (num ^ (t - 1));
}
